package Practice;

import java.util.*;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Text {
    /*找前k个出现频率最高的单词，如果频率一样，先排字典序排序，abc这种
     * */
    public static List<String> topKFrequent(String[] words, int k) {
        //1.遍历数组  统计每个单词出现的频率
        Map<String,Integer> hashMap = new HashMap<>();
        for (String s : words) {
            if (hashMap.get(s) == null) {
                hashMap.put(s,1);
            }else {
                int val = hashMap.get(s);//拿到之前的val值
                hashMap.put(s,val+1);//把value值设置为在原来的基础上+1
            }
        }
        //2.建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(
                k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        }
        );
        //3.遍历hashMap  把里面的数据放到小根堆
        for (Map.Entry<String,Integer> entry : hashMap.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                //小根堆已经放满了k个元素，下一个该和堆顶元素-进行比较了
                Map.Entry<String,Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {
                    //频率相同的情况
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        //按照字典序比较
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        //4.此时小根堆中已经有了结果
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
           String key = minHeap.poll().getKey();
           ret.add(key);
        }
        /*它是操作集合类的一个工具，里面有很多的方法，Arrays是操作数组的，
        * Collections是操作集合的*/
        Collections.reverse(ret);
        return ret;
    }

    public static void main(String[] args) {
        String[] str = {"a","b","c","a","b","c"};
        topKFrequent(str,2);
        System.out.println(str);
    }
    //复制一个带随机指针的链表
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        cur = head;
         while (cur != null) {
             map.get(cur).next = map.get(cur.next);
             map.get(cur).random = map.get(cur.random);
             cur = cur.next;
         }
         return map.get(head);
    }
    //存在重复的元素   数组中任意一个元素至少出现两次，返回true  否则false
    public boolean containsDuplicate(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int x : nums) {
            if (!map.containsKey(x)) {
                map.put(x,1);
            }else {
                int val = map.get(x);
                map.put(x,val+1);
            }
        }
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if (entry.getValue() > 1) {
                return true;
            }
        }
        return false;
    }
    //判断一个数组中是否存在 i和j下标的值相等 &&  abs（i-j）<=k
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (map.containsKey(num) && i - map.get(num) <= k) {
                return true;
            }
            map.put(nums[i],i);
        }
        return false;
    }
    //只出现一次的数字
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            if (!set.contains(x)) {
                set.add(x);
            }else {
                set.remove(x);
            }
        }
        int val = set.hashCode();
        return val;
    }
    //宝石与石头   jewels = "aA", stones = "aAAbbbb"   输出3
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        int count = 0;
        for (int i = 0; i < jewels.length(); i++) {
            set.add(jewels.charAt(i));
        }
        for (int i = 0; i < stones.length(); i++) {
            if (set.contains(stones.charAt(i))) {
                count++;
            }
        }
        return count;
    }

    //坏键盘打字
    public static void func(String str1, String str2) {
        Set<Character> set = new HashSet<>();
        for (char s2 : str2.toUpperCase().toCharArray()) {
            set.add(s2);
        }
        Set<Character> setBroken = new HashSet<>();
        for (char s1 : str1.toUpperCase().toCharArray()) {
            if (!set.contains(s1) && !setBroken.contains(s1)) {
                setBroken.add(s1);
                System.out.print(s1);
            }
        }
    }

    public static void main1(String[] args) {
        Scanner scan = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (scan.hasNextLine()) {
            String str1 = scan.nextLine();
            String str2 = scan.nextLine();
            func(str1, str2);
        }
    }
}
